The present invention relates generally to digital logic. More particularly, the invention relates to a method and apparatus for quickly identifying a lowest or highest boundary value from among a number of values. The invention has particular applications in the field of high-performance digital communications and has other applications.
In a number of digital logic applications, it is necessary to determine the highest value or lowest value number of a group of digitally-encoded numbers. In this application boundary value will be used to indicate either a highest or lowest value. One such application is determining cell or packet scheduling in a digital communications device. In such a device, cells, packets, buffers, or other entities, may each be assigned a number indicating their priority. A scheduling routing selects a cell, packet, buffer or other entity based on its priority value as compared with the priority values of other entities seeking service. In some applications, the priority values associated with a cell, packet, buffer, or other entity are referred to as tags.
Typically, this selection is accomplished using a tree of comparators. FIG. 1 illustrates a prior art method for determining a boundary value out of 16 numbers using four stages of comparators. In the first stage, numbers are paired (in many applications in a fixed order or essentially at random) and input into comparators 10. The boundary higher or lower value of each pair is passed to the next stage and the other value is discarded. For 16 tags, this process is repeated three more times, until one boundary value emerges.
This prior art device has a number of disadvantages. The first is that in a hardware implementation, each comparator is generally comprised of a large number of gates (usually XOR gates) and this consumes a large chip area. As is known in the art, the total chip area needed for a hardware implementation can be reduced by reusing compare elements for different stages, but doing so adds to the complexity of the circuit and increases processing time.
Two other related disadvantages are that it is difficult to determine if more than one of the initial tags is equal to the boundary value and it is difficult to signal to the initial tags or values which of them was selected as the boundary value. This is because the output of the final comparator 10a is simple an N bit number representing the boundary detected. While both of these difficulties can be address in a circuit such as FIG. 1, doing so requires additional feedback circuitry and can also require additional time for processing.
What is needed is a method and apparatus that can select one or more boundary values from a number of input values without the disadvantageous and limitations of prior art methods.
The present invention is a method and apparatus for quickly the maximum or minimum boundary value from a group of values that quickly indicates the output boundary value and indicates each input value that matched that boundary value.
In one embodiment, the invention is constructed of slice logic blocks, each block processing one of the input values to determine if it is a maximum value. A result block, shared by all the logic blocks, produces the boundary value.
The invention also comprises a method for selecting a boundary value by comparing all the bits in one input value to input bits and conditioned bits from other input values.
In a communications device, such as an ATM switch or routing table or other devices, the input values (in this embodiment referred to as tags) may represent a priority level and the device and method of the invention can be used to very quickly determine tags indicating the highest or lowest priority buffers or cells awaiting service.
The invention will be explained with respect to specific embodiments, but will be clear to those of skill in the art that the invention may be deployed in many alternative logic applications. The invention may also be deployed as described below for operation of a wide variety of communications devices. For the sake of clarity, the invention will be described in terms of specific examples. It is inherent in the art that logic devices and processes and communications devices can be highly variable in the arrangement and configuration of different components. These examples should therefore been taken as illustrations and not seen as limiting the invention and the invention should not be limited except as provided by the attached claims and allowable equivalents.